package com.cet.algorithm.二叉树.将有序数组转为高度平衡的二叉搜索树;

import com.cet.algorithm.二叉树.TreeNode;
import com.cet.algorithm.二叉树.TreeOperation;

/**
 * @program: cet-practice
 * @description: 将有序数组转化为高度平衡二叉树
 * @author: 陈恩涛
 * @create: 2023-05-22 13:07
 **/
public class LC108 {

    public TreeNode sortedArrayToBST(int[] nums) {
        return sortedArrayToBST(nums, 0, nums.length -1);
    }

    public TreeNode sortedArrayToBST(int[] nums, int startIndex, int endIndex) {

        // 递归终止条件
        if (startIndex > endIndex) {
            return null;
        }

        // 单层递归逻辑

        // 找到中间位置
        int mid = startIndex + (endIndex - startIndex) / 2;

        // 先序遍历构建二叉树
        TreeNode root = new TreeNode(nums[mid]);

        root.left = sortedArrayToBST(nums, startIndex, mid - 1);
        root.right = sortedArrayToBST(nums, mid + 1, endIndex);

        return root;
    }

    public static void main(String[] args) {
        TreeNode root = new LC108().sortedArrayToBST(new int[]{-10, -3, 0, 5, 9});
        TreeOperation.show(root);
    }
}
